Sponge based cryptography
% Remco Bloemen % 2014-05-11
NSA Suite B and OpenSSL
At Coblue we use NSA Suite B as implemented in OpenSSL as our library for cryptography. Suite B has two security levels which, in proper intelligence agency fashion, are named SECRET and TOP SECRET. Since the we value security more than a slight performance difference, we use the strongest set. This implies using the following four primitives:
- Encryption: 256 bit AES-GCM
- Key exchange: 384 bit ECDH over curve p384
- Signatures: 384 bit ECDSA over curve p384
- Hashing: 384 bit SHA 2
Suite B also involves specific requirements on how to implement and use them. This is written down in various RFC, NIST and FIPS publications, most of which are about implementation details, but I recommend reading NIST SP 800 38D chapter 8, as it sets safety limits on the length of messages, the number of messages and IV generation for AES-GCM.
The choice for the OpenSSL library was made because it supports all the algorithms in Suite B. It is open source and used by the majority of web servers for their cryptography. The project is developed by both European and U.S. based developers and has received NIST FIPS 140 certification. This makes it a reliable, if not the default, choice.
Secure web servers (for https) require at least TLS version 1.2 to support this set of algorithms. Since support was not common at the time, we maintained patches to OpenSSL, Apache and Qt in order to be among the first to support a full Suite B implementation on our web servers and in our software.
To go above and beyond TOP SECRET security we added the Scrypt as a key derivation algorithm, pinned our certificates and developed a simple secure socket protocol that bypassed the complexities of TLS. All of this is packaged in a statically linked native client.
These choices turned out to be foresightful and have saved us and our users from being affected by many high-impact security breaches:
- MD5 and SHA 1: Marc Steven’s attack has made it feasible to break signatures using these hashing algorithms, to proof his concept he created a server with a roque certificate which was accepted by all browsers. Evidence from Flame suggests that intelligence agencies knew about it for longer. Coblue was saved by using SHA 2 and pinning our certificates instead of relying on certificate chains and authorities.
- DigiNotar: This certificate authority was completely compromised allowing the issuing of false certificates. Coblue was again saved by having its certificates pinned.
- BEAST and Lucky 13: These are attacks on the CBC block cipher mode, stream ciphers like AES-GCM were not affected. As a response many servers switched to the RC4 stream cipher. Coblue never used the CBC mode.
- RC4: This stream cipher has already been broken in 2001, which resulted in widespread cracking of WEP keys. Despite this, it is still used (sometimes in slightly modified form) as part of WPA, SSL, BitTorrent, Skype, PDF. Coblue never used RC4. BEAST many web servers (50% according to one source) are using RC4.
- CRIME and BREACH: Like BEAST it allows an attacker to learn about the
- Numerous web browser exploits.
- HeartBleed: This is a bug in OpenSSL’s TLS implementation.
Limitations
- OpenSSL code quality is not nearly up to our standards
- Many primitives: AES, GHASH, SHA256, HMAC, PBKDF2, ECDH, ECDSA
- SHA length extension, requiring workarounds in HMAC and PBKDF2.
- Development of side-channel attacks
- NSA is known to manipulate standards and P-384 is suspect
Comparison
Security
Implementation maturity
Lines of code
OpenSSL itself has about 4 hundred thousand lines of code in total, most of these are not used in our
sloccount crypto/modes/{ctr128,gcm128,ghash-x86_64}.*
crypto/aes/aes_{ctr,misc}.c crypto/aes/aes_{core,ctr,misc,wrap}.*
crypto/aes/*.s crypto/aes/asm/*aes-x86_64.pl crypto/aes/asm/aesni-x86_64.pl
sloccount crypto/sha/sha{,256,256-x86_64,256t,_dgst}.*
crypto/sha/asm/sha512-x86_64.pl
The OpenSSL code consists of Ansi C, Assebler and Perl scripts to produce the assembler.
Performance
Benchmarking
Results
var labels = ['SHA 256', 'Keccak', 'AES-GCM', 'SpongeWrap'];
columnChart(labels, [2700, 3500, 14000, 31000]);
columnChart(labels, [13.0, 13.7, 2.5, 3.8]);
Conclusion
Algorithm LoC Setup cost Cycles per byte
SHA 256 2285 2700 13.0 Keccak 429⁽¹⁾ 3500 13.7 AES-GCM 21560 14000 2.5 SpongeWrap 554⁽¹⁾ 31000 3.8
(1): 308 lines of code are shared between these implementations. These lines represent the Keccak permutation function and the core of both algorithms.